# 公因数匹配(好题)
import heapq
import math
from collections import defaultdict

from leetcode import test_function as tf


def match_gcd_bf(arr):
    """使用暴力法, 超时/通过 = 4/5"""
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if math.gcd(arr[i], arr[j]) > 1:
                print(str(i + 1) + " " + str(j + 1))
                return i + 1, j + 1


def match_gcd_fake_opt(arr):
    """
    一个非常好的写法
    基本定理: 任何一个正整数都可以拆成若干个质数的乘积, 即 a = p1 * p2 * p3 .... * pn
    若 a = pi1 * pi2 * .... * pn
      b = pj1 * pj2 * .... * pm
    可以看到a和b的公因子就是既能由组成a的若干质数表示, 也能由b的若干质数表示.
    那么两者只要包含一个相同的质数, 那么他们的公因子就大于1.
    虽然想法很好, 但是计算用时比暴力算法更高
    """

    def sieve(num: int):
        """
        埃拉托斯特尼筛法：求出小于等于 n 的所有质数
        """
        is_prime = [True] * (num + 1)
        is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数
        # 从 2 到 sqrt(n) 进行筛选
        for i in range(2, int(math.sqrt(num)) + 1):
            if is_prime[i]:
                # 将 i 的倍数标记为非质数
                for j in range(i * i, num + 1, i):
                    is_prime[j] = False
        # 返回所有质数的列表
        return [i for i, prime in enumerate(is_prime) if prime]

    max_num = max(arr)
    primes = sieve(max_num)
    pos = [0] * (max_num + 1)
    res1, res2 = n + 1, -1
    for idx, num in enumerate(arr, start=1):
        l = len(arr) + 1
        for prime in primes:
            if prime > num:
                break
            if num % prime == 0:
                while num % prime == 0:
                    num //= prime
                if pos[prime]:
                    l = min(l, pos[prime])
                else:
                    pos[prime] = idx

        if num > 1:
            if pos[num]:
                l = min(l, pos[num])
            else:
                pos[num] = idx

        if l < res1:
            res1 = l
            res2 = idx

    print(str(res1) + " " + str(res2))
    return res1, res2


def match_gcd_opt(arr):
    """
    通过分解所有元素的因数, 来找到两个共同因数大于1的索引.
    首先对每个元素进行因数分解，记录所有因数（包括重复因数），使用一个dict来记录{因数:[元素索引]}
    遍历dict来找到有公因数的两个元素的索引
    """
    index = defaultdict(list)
    # 对每个元素进行因数分解
    for i, num in enumerate(arr):
        for fact in range(2, int(num ** 0.5) + 1):
            if num % fact == 0:
                heapq.heappush(index[fact], i + 1)
                heapq.heappush(index[num // fact], i + 1)
        heapq.heappush(index[num], i + 1)
    min_i = float('inf')
    min_j = float('inf')

    for facts in index.values():
        if len(facts) > 1:
            if facts[0] < min_i:
                min_i = facts[0]
                min_j = facts[1]
            elif facts[0] == min_i:
                min_j = min(min_j, facts[1])
    return min_i, min_j


if __name__ == '__main__':
    # n = int(input())
    # inp = list(map(int, input().split()))
    # match_gcd_bf(inp)

    with open("../../data/2023_f.in", "r") as file:
        n = int(file.readline())
        lst = list(map(int, file.readline().split()))
    inp = [{"arr": [5, 3, 2, 6, 9]}, {"arr": lst}]
    out = [(2, 4), (10665, 13722)]
    # tf(match_gcd_bf, inp, out)  # 21.143666s
    # tf(match_gcd_fake_opt, inp, out)  # 71.670004s
    tf(match_gcd_opt, inp, out)  # 0.736115s
